package a4_p04_jw_kw.searchalgo;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import org.jgrapht.Graph;
import org.jgrapht.Graphs;
import org.jgrapht.graph.DefaultWeightedEdge;

import a1_p04_jw_kw.struct.Node;

public class HolzerDFS {
	Stack<Node> stack = new Stack<Node>();
	Graph<Node, DefaultWeightedEdge> g;
	List<Node> visited = new ArrayList<Node>();

	ArrayList<Node> myWay = new ArrayList<Node>();

	Node startNode;

	public HolzerDFS(Graph<Node, DefaultWeightedEdge> g) {
		this.g = g;

	}

	public void startSearch(String node) {
		this.startNode = getNode(node);
		startNode.parent = null;
		myWay = dfs(startNode);

	}

	private ArrayList<Node> dfs(Node start) {

		stack.push(start);

		while (!stack.isEmpty()) {
			Node actualNode = stack.peek();
//			System.out.println("Aktueller Knoten " + actualNode);
			visited.add(actualNode);
//			System.out.println("added " + actualNode + " to visitedList");
			stack.pop(); // aktuellen Knoten entfernen

			if (actualNode.equals(start) && start.parent != null) {
//				System.out.println("actualNode = start & parent != null");
				return getWay(actualNode);
			}

			ArrayList<Node> successorList = new ArrayList<Node>();
			successorList = getSuccessors(actualNode);

//			System.out.println("erstelle Nachfolger: " + successorList);

			if (successorList.isEmpty()) {
//				System.out.println(" successors leer");
				continue;
			}

			for (Node node : successorList) {
				node.parent = actualNode.name;
//				System.out.println("lege : " + node + " auf den Stack");
				stack.push(node);
			}

		}

		return null;
	}

	private ArrayList<Node> getWay(Node actualNode) {

		ArrayList<Node> way = new ArrayList<Node>();
		Node tmp = actualNode;

		while (tmp.parent != startNode.name) {
			way.add(tmp);
			tmp = getNode(tmp.parent);
		}
		way.add(tmp);
		way.add(getNode(tmp.parent));

		return way;
	}

	private ArrayList<Node> getSuccessors(Node node) {

		ArrayList<Node> successor = new ArrayList<Node>();

//		System.out.println("aktueller Knoten: " + node.name + " visitedList: " + visited);

		for (Node target : Graphs.neighborListOf(this.g, node)) {

			// Target ist nicht auf visited
			if (!visited.contains(target)) {
				successor.add(target);
//				System.out.println("-> " + target.name + " added");
			}else {
//				System.out.println("-> " + target.name + " verworfen");
			}

			// target = Ziel und target parent nicht Startknoten
			if (target.equals(startNode) && node.parent != startNode.name) {
				successor.add(target);
//				System.out.println(target.name + " ist Zielknoten, daher added, obwohl auf visited List");
			}
		}

		return successor;
	}

	private Node getNode(String name) {
		for (Node node : g.vertexSet()) {
			if (node.name.equals(name)) {
				return node;

			}
		}

		return null;
	}

	public Stack<Node> getStack() {
		return stack;
	}

	public List<Node> getVisited() {
		return visited;
	}

	public ArrayList<Node> getWay() {
		return myWay;
	}

	public Node getStartNode() {
		return startNode;
	}
}
